home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_300 / 317_01 / g4sencod.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-06-16  |  11.2 KB  |  364 lines
  1. /*    $Id: g4sencod.c 1.2 90/06/09 18:24:10 marking Exp $
  2.  *
  3.  NAME
  4.  *    g4sencod.c -- encode group 4 data using nested if statements
  5.  *
  6.  TYPE
  7.  *    C procedures
  8.  *
  9.  SYNOPSIS
  10.  *    char    g4j_encode_black (short runlength);
  11.  *    char    g4j_encode_white (short runlength);
  12.  *    char    g4j_encode_EOFB (void);
  13.  *    char    g4j_encode_new_row (void);
  14.  *    char    g4j_initialize (short image_width, short image_length);
  15.  *
  16.  DESCRIPTION
  17.  *    Routines to encode group 4 images. Consecutive calls to encode
  18.  *    black or white runs will be combined.
  19.  *
  20.  RETURNS
  21.  *
  22.  LEGAL
  23.  *    Copyright 1989, 1990 Michael P. Marking, Post Office Box 8039,
  24.  *    Scottsdale, Arizona 85252-8039. All rights reserved.
  25.  *
  26.  *    License is granted by the copyright holder to distribute and use this
  27.  *    code without payment of royalties or the necessity of notification as
  28.  *    long as this notice (all the text under "LEGAL") is included.
  29.  *
  30.  *    Reference: $Id: g4sencod.c 1.2 90/06/09 18:24:10 marking Exp $
  31.  *
  32.  *    This program is offered without any warranty of any kind. It includes
  33.  *    no warranty of merchantability or fitness for any purpose. Testing and
  34.  *    suitability for any use are the sole responsibility of the user.
  35.  * 
  36.  HISTORY
  37.  *    $Log:    g4sencod.c $
  38.  * Revision 1.2  90/06/09  18:24:10  marking
  39.  * clean up comments for release
  40.  * 
  41.  * Revision 1.1  90/05/01  02:00:00  marking
  42.  * Initial revision
  43.  * 
  44.  *
  45.  NOTES
  46.  *
  47.  PORTABILITY
  48.  *    Tested using Microsoft C 5.1. Some memory models may not work due to
  49.  *    the large encoding arrays.
  50.  *
  51.  *    There is a non-portable use of "global" variables in the file g3g4.h,
  52.  *    about which a minority of compilers will justifiably complain. Certain
  53.  *    variables are declared in g3g4.h without extern keywords. Strictly
  54.  *    speaking, they should be declared extern in all but one module, but
  55.  *    that would require complication of g3g4.h. If it gets past your
  56.  *    compiler and linker, you can probably ignore it.
  57.  *
  58.  SEE ALSO
  59.  *
  60.  INFORMATION
  61.  *    Although there is no support offered with this program, the author will
  62.  *    endeavor to correct errors. Updates will also be made available from
  63.  *    time to time.
  64.  *
  65.  *    Contact: Michael P. Marking, Post Office Box 8039, Scottsdale, Arizona
  66.  *    85252-8039 USA. Replies are not guaranteed to be swift. Beginning
  67.  *    July 1990, e-mail may be sent to uunet!ipel!marking.
  68.  *
  69.  *    Also beginning in July 1990, this code will be archived at the
  70.  *    ipel!phoenix BBS in file g3g4.zoo. The 24-hour telephone number
  71.  *    for 300/1200/2400 is (602)274-0462. When logging in, specify user
  72.  *    "public", system "bbs", and password "public".
  73.  *
  74.  *    This code is also available from the C Users Group in volume 317.
  75.  */
  76.  
  77. #include "g3g4.h"
  78.  
  79. /* #define TRACE 1 */
  80.  
  81. /* implementation limits: Due to the sizes of arrays and variables, and not
  82.    due to any restrictions in the algorithm, the following limits exist:
  83.      maximum number of pixels per row: 65533
  84.      maximum number of rows per image: none
  85.      maximum or minimum k-factor: none
  86.      maximum number of runs per row: 16382 white, 16382 black
  87.    To increase (or decrease) these limits, it will be necessary to play with
  88.    array and variable sizes.  On segmented machines (such as the 8086), a
  89.    different memory model may be necessary.  The algorithm itself has no
  90.    limits on image size or complexity, and the stack requirements are in-
  91.    sensitive to changes in these limits or to image complexity. */
  92.  
  93. #define EVEN 0
  94. #define ODD 1
  95.  
  96. static short a0, a1, a2, b0, b1, b2, length_of_current_run;
  97. static unsigned char color, current_row, mode;
  98. static short even_runs [32768], odd_runs [32768];
  99. static unsigned short reference_index, coding_index;
  100. static short *reference_line, *coding_line;
  101. static short column_limit;
  102.   /* Depending as current_row == EVEN or current_row == ODD, the runs of the
  103.      current row are represented in even_runs [] or odd_runs [].  The white
  104.      runs have even subscripts and the black runs have odd subscripts.  The
  105.      values of the array elements are the offsets of the beginnings of the
  106.      corresponding runs from the beginning of the row.  As defined by the
  107.      specification,
  108.     a0 is the reference or starting changing element on the coding line.
  109.         It may be considered the "current position".
  110.     a1 is the next changing element to the right of a0 on the coding line.
  111.     a2 is the next changing element to the right of a1 on the coding line.
  112.     b1 is the first changing element on the reference line to the right of
  113.         a0 and of opposite color to a0.
  114.     b2 is the next changing element to the right of b1 on the reference
  115.         line.
  116.      Furthermore,
  117.     b0 is the "previous" value of b1. 
  118.      */
  119.  
  120. char g4j_initialize (short image_width, short image_length)
  121. {
  122.   initialize_encode ();
  123.   color = WHITE;
  124.   current_row = ODD;
  125.   coding_line = odd_runs;
  126.   reference_line = even_runs;
  127.   coding_index = 0;
  128.   coding_line [0] = 0;
  129.   length_of_current_run = 0;
  130.   column_limit = image_width;
  131.   reference_line [0] = 0;
  132.   reference_line [1] = column_limit;
  133.   reference_line [2] = column_limit;
  134.   reference_line [3] = column_limit;
  135.   return (0);
  136. }
  137.  
  138. char g4j_encode_EOFB ()
  139. {
  140.   encode_word (EOL_code, EOL_length);
  141.   encode_word (EOL_code, EOL_length);
  142.   return (0);
  143. }
  144.  
  145. char g4j_encode_new_row ()
  146. {
  147.   short last_point;
  148.   last_point  = coding_line [coding_index] + length_of_current_run;
  149.   coding_index++;
  150.   coding_line [coding_index] = last_point;
  151.   coding_line [coding_index + 1] = last_point;
  152.   coding_line [coding_index + 2] = last_point;
  153.   coding_line [coding_index + 3] = last_point;
  154.   /* encode the current row */
  155.   #if defined (TRACE)
  156.     if (trace_flag)
  157.     {
  158.       short j = 0, a;
  159.       printf (" coding_line = < ");
  160.       while ((a = coding_line [j]) < column_limit)
  161.       {
  162.         printf ("%hd@%hd ", (short) (coding_line [j + 1] - a), a);
  163.         j++;
  164.       }
  165.       printf ("> ");
  166.       j = 0;
  167.       printf ("\nreference_line = < ");
  168.       while ((a = reference_line [j]) < column_limit)
  169.       {
  170.         printf ("%hd@%hd ", (short) (reference_line [j + 1] - a), a);
  171.         j++;
  172.       }
  173.       printf ("> ");
  174.     };
  175.   #endif
  176.   reference_index = 0;
  177.   coding_index = 0;
  178.   a1 = coding_line [0];
  179.   a2 = coding_line [1];
  180.   if (a2 == 0 && reference_line [1] == 0)
  181.     /* if the first (white) run is null as was in previous row */
  182.   {
  183.     encode_word (VERTICAL_V0_CODEWORD, VERTICAL_V0_CODELEN);
  184.     coding_index++;
  185.     a1 = coding_line [1];
  186.     a2 = coding_line [2];
  187.     #if defined (TRACE)
  188.       if (trace_flag) printf ("V0 ");
  189.     #endif
  190.   }
  191.   while (a1 < column_limit)
  192.   {
  193.     short effective_a0;
  194.     a0 = a1;
  195.     a1 = a2;
  196.     a2 = coding_line [coding_index + 2];
  197.     if (reference_index > 3) reference_index -= 3;
  198.     else reference_index = 0;
  199.     if (coding_index) effective_a0 = a0;
  200.     else effective_a0 = -1;
  201.     while (effective_a0 >= (b1 = reference_line [reference_index]))
  202.       reference_index++;
  203.       /* now the reference index points to the first changing point beyond a0,
  204.      but it may or may not be the same color as a0 */
  205.     if (! ((coding_index ^ reference_index) & 1)) /* if same colors */
  206.     {
  207.       reference_index++; /* now different color */
  208.       b1 = reference_line [reference_index];
  209.     }
  210.     b2 = reference_line [reference_index + 1];
  211.     #if defined (TRACE)
  212.       if (trace_flag)
  213.         printf ("\na0=%hd a1=%hd a2=%hd b1=%hd b2=%hd rx=%hd cx=%hd ",
  214.       a0, a1, a2, b1, b2, reference_index, coding_index);
  215.     #endif
  216.     while (b2 < a1) /* PASS */
  217.     {
  218.       #if defined (TRACE)
  219.     short old_a0 = a0;
  220.       #endif
  221.       encode_word (PASS_CODEWORD, PASS_CODELEN);
  222.       a0 = b2;
  223.       reference_index += 2;
  224.       b1 = reference_line [reference_index];
  225.       b2 = reference_line [reference_index + 1];
  226.       #if defined (TRACE)
  227.         if (trace_flag) printf ("PASS k%hd ", (short) (a0 - old_a0));
  228.       #endif
  229.     }
  230.     if (a1 == b1) /* V0 */
  231.     {
  232.       encode_word (VERTICAL_V0_CODEWORD, VERTICAL_V0_CODELEN);
  233.       coding_index++;
  234.       #if defined (TRACE)
  235.         if (trace_flag) printf ("V0 ");
  236.       #endif
  237.     }
  238.     else if (a1 == b1 + 1) /* VR1 */
  239.     {
  240.       encode_word (VERTICAL_VR1_CODEWORD, VERTICAL_VR1_CODELEN);
  241.       coding_index++;
  242.       #if defined (TRACE)
  243.         if (trace_flag) printf ("VR1 ");
  244.       #endif
  245.     }
  246.     else if (a1 == b1 + 2) /* VR2 */
  247.     {
  248.       encode_word (VERTICAL_VR2_CODEWORD, VERTICAL_VR2_CODELEN);
  249.       coding_index++;
  250.       #if defined (TRACE)
  251.         if (trace_flag) printf ("VR2 ");
  252.       #endif
  253.     }
  254.     else if (a1 == b1 + 3) /* VR3 */
  255.     {
  256.       encode_word (VERTICAL_VR3_CODEWORD, VERTICAL_VR3_CODELEN);
  257.       coding_index++;
  258.       #if defined (TRACE)
  259.         if (trace_flag) printf ("VR3 ");
  260.       #endif
  261.     }
  262.     else if (a1 == b1 - 1) /* VL1 */
  263.     {
  264.       encode_word (VERTICAL_VL1_CODEWORD, VERTICAL_VL1_CODELEN);
  265.       coding_index++;
  266.       #if defined (TRACE)
  267.         if (trace_flag) printf ("VL1 ");
  268.       #endif
  269.     }
  270.     else if (a1 == b1 - 2) /* VL2 */
  271.     {
  272.       encode_word (VERTICAL_VL2_CODEWORD, VERTICAL_VL2_CODELEN);
  273.       coding_index++;
  274.       #if defined (TRACE)
  275.         if (trace_flag) printf ("VL2 ");
  276.       #endif
  277.     }
  278.     else if (a1 == b1 - 3) /* VL3 */
  279.     {
  280.       encode_word (VERTICAL_VL3_CODEWORD, VERTICAL_VL3_CODELEN);
  281.       coding_index++;
  282.       #if defined (TRACE)
  283.         if (trace_flag) printf ("VL3 ");
  284.       #endif
  285.     }
  286.     else /* HORIZONTAL */
  287.     {
  288.       short first_run, second_run;
  289.       encode_word (HORIZONTAL_CODEWORD, HORIZONTAL_CODELEN);
  290.       first_run = a1 - a0;
  291.       second_run = a2 - a1;
  292.       if (coding_index & 1) /* if BLACK, WHITE */
  293.       {
  294.     g3j_encode_black (first_run);
  295.     g3j_encode_white (second_run);
  296.     #if defined (TRACE)
  297.       if (trace_flag) printf ("B%hd W%hd ", first_run, second_run);
  298.     #endif
  299.       }
  300.       else /* WHITE, BLACK */
  301.       {
  302.     g3j_encode_white (first_run);
  303.     g3j_encode_black (second_run);
  304.     #if defined (TRACE)
  305.       if (trace_flag) printf ("W%hd B%hd ", first_run, second_run);
  306.     #endif
  307.       }
  308.       coding_index++;
  309.       a0 = a1;
  310.       a1 = a2;
  311.       a2 = coding_line [coding_index + 2];
  312.       coding_index++;
  313.       #if defined (TRACE)
  314.         if (trace_flag) printf ("HORIZ ");
  315.       #endif
  316.     }
  317.   }
  318.   /* now swap rows */
  319.   if (current_row == EVEN)
  320.   {
  321.     current_row = ODD;
  322.     coding_line = odd_runs;
  323.     reference_line = even_runs;
  324.   }
  325.   else /* current_row == ODD */
  326.   {
  327.     current_row = EVEN;
  328.     coding_line = even_runs;
  329.     reference_line = odd_runs;
  330.   }
  331.   coding_index = 0;
  332.   coding_line [coding_index] = 0;
  333.   length_of_current_run = 0;
  334.   return (0);
  335. }
  336.  
  337. char g4j_encode_black (short runlength)
  338. {
  339.   if (!(coding_index & 1)) /* if even number, is white */
  340.   {
  341.     coding_index++; /* move on to black */
  342.     coding_line [coding_index]
  343.       = coding_line [coding_index - 1] + length_of_current_run;
  344.     length_of_current_run = 0;
  345.   }
  346.   length_of_current_run += runlength;
  347.   return (0);
  348. }
  349.  
  350. char g4j_encode_white (short runlength)
  351. {
  352.   if (coding_index & 1) /* if odd number, is black */
  353.   {
  354.     coding_index++; /* move on to white */
  355.     coding_line [coding_index]
  356.       = coding_line [coding_index - 1] + length_of_current_run;
  357.     length_of_current_run = 0;
  358.   }
  359.   length_of_current_run += runlength;
  360.   return (0);
  361. }
  362.  
  363. /*    end $RCSfile: g4sencod.c $ */
  364.